//
//  Tree.c
//  AlgorithmLearning
//
//  Created by aron on 2017/11/9.
//  Copyright © 2017年 aron. All rights reserved.
//

#include "Tree.h"
#include <stdlib.h>

SearchTree Tree_MakeEmpty(SearchTree T) {
    if (NULL != T) {
        Tree_MakeEmpty(T->Left);
        Tree_MakeEmpty(T->Right);
        free(T);
    }
    return NULL;
}

Position Tree_Find(ElementType Element, SearchTree T) {
    if (NULL == T) {
        return NULL;
    }
    if (Element < T->Element) {
        return Tree_Find(Element, T->Left);
    }
    if (Element > T->Element) {
        return Tree_Find(Element, T->Right);
    }
    return T;
}

// 查找最大
Position Tree_FindMax(SearchTree T) {
    if (NULL == T) {
        return NULL;
    }
    if (T->Right) {
        return Tree_FindMax(T->Right);
    }
    return T;
}

// 查找最小
Position Tree_FindMin(SearchTree T) {
    if (NULL == T) {
        return NULL;
    }
    if (T->Left) {
        return Tree_FindMin(T->Left);
    }
    return T;
}

// 插入
SearchTree Tree_Insert(ElementType Element, SearchTree T) {
    if (NULL == T) {
        T = malloc(sizeof(struct TreeNode));
        T->Element = Element;
        T->Count = 1;
        // 左右子树置为空
        T->Left = T->Right = NULL;
    } else if (Element < T->Element) {
        T->Left = Tree_Insert(Element, T->Left);
    } else if (Element > T->Element) {
        T->Right = Tree_Insert(Element, T->Right);
    } else {
        T->Count ++;
    }
    // 返回最终插入的位置
    return T;
}

// 删除
// 有两个子树的情况，查找右孩子节点的最小值，并且删除它
SearchTree Tree_Delete(ElementType Element, SearchTree T) {
    if (NULL == T) {
        return T;
    }
    
    Position Tmp;
    if (Element < T->Element) {
        // T->Left = XX ！！更新指针的操作需要添加，子树的根节点有可能有变化，需要修改父节点指针的指向
        T->Left = Tree_Delete(Element,T->Left);
    } else if (Element > T->Element) {
        T->Right = Tree_Delete(Element,T->Right);
    }
    // 找到删除的节点
    else if(T->Left && T->Right) {
        // A 有两个孩子节点
        // 查找右孩子节点的最小值，
        // 右孩子节点的最小值没有左孩子节点，并且比左子树所有节点的值都大，比右子树其他节点的值都小
        // 所以可以使用这个节点替换要删除的节点
        Tmp = Tree_FindMin(T->Right);
        T->Element = Tmp->Element;
        // 从右子树中删除该节点，因为没有左孩子，所以这个删除的步骤会走到【有一个孩子节点或者0个孩子节点】这个分支
        // 更新右子树的指针
        T->Right = Tree_Delete(Tmp->Element, T->Right);
    } else {
        // B 有一个孩子节点或者0个孩子节点
        Tmp = T;
        if (NULL == T->Left) {
            T = T->Right;
        } else if (NULL == T->Right) {
            T = T->Left;
        }
        free(Tmp);
    }
    return T;
}

// 删除
// 有两个子树的情况，查找左孩子节点的最大值，并且删除它
SearchTree Tree_Delete2(ElementType Element, SearchTree T) {
    if (NULL == T) {
        return T;
    }
    
    Position Tmp;
    if (Element < T->Element) {
        // T->Left = XX ！！更新指针的操作需要添加，子树的根节点有可能有变化，需要修改父节点指针的指向
        T->Left = Tree_Delete2(Element,T->Left);
    } else if (Element > T->Element) {
        T->Right = Tree_Delete2(Element,T->Right);
    }
    // 找到删除的节点
    else if(T->Left && T->Right) {
        // A 有两个孩子节点
        // 查找左孩子节点的最大值，
        // 左孩子节点的最大值没有左孩子节点，并且比右子树所有节点的值都小，比左子树其他节点的值都大
        // 所以可以使用这个节点替换要删除的节点
        Tmp = Tree_FindMax(T->Left);
        T->Element = Tmp->Element;
        // 从左子树中删除该节点，因为没有右孩子，所以这个删除的步骤会走到【有一个孩子节点或者0个孩子节点】这个分支
        // 更新左子树的指针
        T->Left = Tree_Delete2(Tmp->Element, T->Left);
    } else {
        // B 有一个孩子节点或者0个孩子节点
        Tmp = T;
        if (NULL == T->Left) {
            T = T->Right;
        } else if (NULL == T->Right) {
            T = T->Left;
        }
        free(Tmp);
    }
    return T;
}

// Left->Middle->Right 中序遍历
void Tree_LMR_Travel(SearchTree T) {
    if (NULL == T) {
        return;
    }
    if(NULL != T->Left) Tree_LMR_Travel(T->Left);
    int i;
    for (i= 0; i<T->Count; i++) {
        printf("%d ", T->Element);
    }
    if(NULL != T->Right) Tree_LMR_Travel(T->Right);
}
